#include <gtest/gtest.h>
#include "common.h"
#include <stack>

using namespace ::std;

template <typename T = int>
void printVec(vector<T>& out) {
    for_each(out.begin(), out.end(), [=](T x) { cout << x << " "; });
    cout << endl;
}

void printBinary(TreeNode* root) {
	vector<int> out = makeBinaryTreeToVector(root);
	printVec(out);
}

vector<int> makeBinaryTreeToVec(TreeNode* root) {
    if(nullptr == root) return {};
    vector<int> vec;
    deque<TreeNode*> que;
    vec.push_back(root->val);
    que.push_back(root);
    while(!que.empty()) {
        TreeNode* cursor = que.front();
        que.pop_front();

        if(cursor->left) {
            que.push_back(cursor->left);
            vec.push_back(cursor->left->val);
        } else {
            vec.push_back(INT_MAX);
        }
        if(cursor->right) {
            que.push_back(cursor->right);
            vec.push_back(cursor->right->val);
        } else {
            vec.push_back(INT_MAX);
        }
    }

    for(vector<int>::reverse_iterator it = vec.rbegin(); it != vec.rend() && *it == INT_MAX; ++it) {
        vec.pop_back();
    }
    return vec;
}

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
		vector<int> vecP = makeBinaryTreeToVec(p);
		vector<int> vecQ = makeBinaryTreeToVec(q);
		return vecP == vecQ;
    }
};

class IsSameTreeCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(IsSameTreeCheck, testIsSameTree_1) {
	vector<int> vecP = {1,2,3}, vecQ = {1,2,3};
	TreeNode* p = makeVectorToBinaryTree(vecP);
	TreeNode* q = makeVectorToBinaryTree(vecQ);
	EXPECT_TRUE(true == (solution.isSameTree(p, q)));
}

TEST_F(IsSameTreeCheck, testIsSameTree_2) {
	vector<int> vecP = {1,2}, vecQ = {1,INT_MAX,2};
	TreeNode* p = makeVectorToBinaryTree(vecP);
	TreeNode* q = makeVectorToBinaryTree(vecQ);
	EXPECT_TRUE(false == (solution.isSameTree(p, q)));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
